package tree.heap.arrayUse0IndexHeap;

import pojo.UserVO;

import java.util.*;

/**
 * 功能描述: 手写堆, 堆上的元素调整了, 命中了对应的排序规则, 然后调整堆, 满足排序规则
 *  需要借助一个Map<T,Integer> 存储元素在堆中的位置,  value 为 元素在堆中的位置list中的位置
 * 2024/05/27
 *
 *
 * ZhangYi
 */
public class HeapArrayAdjustUtils {

    public static class HeapAdjustUtils<T>{
        private int heapSize;

        private List<T> dataList;

        private int limitSize=1000;
        private Comparator<T> comparator;

        private Map<T,Integer> map; // 维护元素在堆中的位置,很重要, push , pop, swapValue 都需要维护

        public HeapAdjustUtils(Comparator<T> comparator) {
            this.heapSize = 0;

            this.dataList = new ArrayList<>();

            this.comparator = comparator;

            this.map = new HashMap<>();
        }

        public HeapAdjustUtils(Comparator<T> comparator,
                               int limitSize) {
            this.heapSize = 0;
            this.dataList = new ArrayList<>();
            this.comparator = comparator;
            this.limitSize = limitSize;
            this.map = new HashMap<>();
        }

        public boolean isEmpty(){
            return this.dataList.size() == 0;
        }

        public boolean isFull(){
            return this.dataList.size() == this.limitSize;
        }
        public void push(T val){
            if (val == null){
                throw new RuntimeException("val is null");
            }
            if (isFull()){
                throw new RuntimeException("heap is full,push refuse!");
            }
            this.dataList.add(val);
            map.put(val,heapSize);
            System.out.println(val.hashCode());
            heapInsert(heapSize++);
        }

        public T pop(){
            if (isEmpty()){
                throw new RuntimeException("heap is empty");
            }

            T ans = this.dataList.get(0);
            swapValue(0,--heapSize);
            heapfiy(0,heapSize);
            map.remove(ans); // 从map中移除, 因为在堆中已经不存在了
            return ans;
        }


        public void resign(T val){
            if (val == null){
                return;
            }
            System.out.println(val.hashCode());
            if (!map.containsKey(val)){ // 这个调用的是 对象上的equals方法
                return;
            }

            Integer index = map.get(val);
            heapInsert(index); // 这个只会自下而上的调整堆
            heapfiy(0,heapSize);// 这个只会自上而下的调整堆
        }

        private void heapfiy(int index,
                             int heapSize) {
            int leftIndex = (index << 1) |1 ;
            while (leftIndex < heapSize){
                int smallestIndex = leftIndex +1 < heapSize && this.comparator.compare(this.dataList.get(leftIndex+1),this.dataList.get(leftIndex)) <0 ?
                        leftIndex +1 : leftIndex;

                smallestIndex = this.comparator.compare(this.dataList.get(smallestIndex),this.dataList.get(index)) < 0 ?
                        smallestIndex : index;

                if (smallestIndex == index){
                    break;
                }
                swapValue(index,smallestIndex);
                index = smallestIndex;
                leftIndex = (index << 1) |1 ;
            }
        }

        private void heapInsert(int index) {
            while (this.comparator.compare(this.dataList.get(index), this.dataList.get((index-1) / 2)) < 0 ){
                swapValue(index, (index-1) / 2);
                index = (index-1) / 2;
            }
        }

        private void swapValue(int index,
                               int index2) {
            T temp = this.dataList.get(index);
            this.dataList.set(index, this.dataList.get(index2));
            this.dataList.set(index2, temp);

            map.put(this.dataList.get(index), index);
            map.put(this.dataList.get(index2), index2);
        }
    }

    public static Comparator userComparator() {
        return new Comparator<UserVO>() {
            @Override
            public int compare(UserVO o1,
                               UserVO o2) {
                return o1.getUserName() != null && o2.getUserName() != null ?
                        o1.getUserName().compareTo(o2.getUserName()) :
                        o1.getNickName().compareTo(o2.getNickName());
            }
        };
    }

    public static void main(String[] args) {
        HeapAdjustUtils heapAdjustUtils = new HeapAdjustUtils<UserVO>(userComparator());

        List<UserVO> userList = generateUserList();

        userList.forEach(item->{
            heapAdjustUtils.push(item);
        });

        UserVO user = userList.get(1);
        user.setUserName("张是哪100");
        heapAdjustUtils.resign(user);
        System.out.println(1);
    }

    private static List<UserVO> generateUserList() {
        List<UserVO> userList = new ArrayList<>();
        userList.add(new UserVO("1","张三"));
        userList.add(new UserVO("2","李四"));
        userList.add(new UserVO("3","王五"));
        userList.add(new UserVO("4","赵六"));
        userList.add(new UserVO("5","孙七"));
        userList.add(new UserVO("6","周八"));
        return userList;
    }
}
